package com.zlk.algorithm.huawei.leetcode.list;

import com.zlk.algorithm.util.ListNode;
import org.junit.Test;

/**
 * @program: algorithm
 * @ClassName Code17_isPalindrome
 * @description:是否回文
 * @author: slfang
 * @create: 2025-01-07 14:44
 * @Version 1.0
 **/
public class Code17_isPalindrome {

    //快慢指针
    // 0 1 2 3 4 5
    public boolean isPalindrome(ListNode head) {
        if(head==null){
            return false;
        }
        if(head!=null&&head.next==null){
            return true;
        }
        ListNode slow = head.next;
        ListNode fast = head.next.next;
        if(fast==null){
            return head.val==head.next.val;
        }

        while (fast.next!=null&&fast.next.next!=null){
            slow =slow.next;
            fast = fast.next.next;
        }
        ListNode rHead = slow.next;
        ListNode pre = null;
        if(fast.next==null){//奇数
            pre = slow;
        }else{//偶数
            pre=null;
        }
        slow.next = null;
        //反转链表
        while (rHead!=null){
            ListNode next = rHead.next;
            rHead.next = pre;
            pre = rHead;
            rHead = next;
        }
        rHead = pre;
        while (rHead!=null&&head!=null){
            if(rHead.val!=head.val){
                return false;
            }
            rHead = rHead.next;
            head = head.next;
        }
        return true;
    }

    @Test
    public void test(){
        ListNode headA = new ListNode(1);
        //headA.next = new ListNode(2);
        isPalindrome(headA);
    }

}
